import java.util.ArrayList;

/**
 * @author 雷明浩
 * @date 2025/7/3 10:10
 */
public class Permute {
    // 没有重复项数字的全排列
    // https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private boolean[] vis;
    private ArrayList<ArrayList<Integer>> ret;
    private ArrayList<Integer> path;
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        // write code here
        int len = num.length;
        vis = new boolean[len];
        ret = new ArrayList<ArrayList<Integer>>();
        path = new ArrayList<>();
        dfs(num);
        return ret;
    }

    private void dfs(int[] num) {
        if (path.size() == num.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!vis[i]) {
                vis[i] = true;
                path.add(num[i]);
                dfs(num);
                vis[i] = false;
                path.remove(path.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        Permute permute = new Permute();
        int[] num = {1,2,3};
        permute.permute(num);
    }
}